package com.example.leetdemo.finash;

import java.util.*;

public class Solution380 {

    static class RandomizedSet {

        private Map<Integer, Integer> indexMap;

        private Set<Integer> emptySet;

        private List<Integer> list;

        public RandomizedSet() {
            this.indexMap = new HashMap<>();
            this.list = new ArrayList<>();
            this.emptySet = new HashSet<>();
        }

        public boolean insert(int val) {
            if (indexMap.containsKey(val)) {
                return false;
            }
            Iterator<Integer> index = emptySet.iterator();
            if (index.hasNext()) {
                int key = index.next();
                list.set(key, val);
                indexMap.put(val, key);
            } else {
                list.add(val);
                indexMap.put(val, list.size() - 1);
            }
            return true;
        }

        public boolean remove(int val) {
            if (indexMap.containsKey(val)) {
                list.set(indexMap.get(val), null);
                emptySet.add(indexMap.get(val));
                indexMap.remove(val);
                return true;
            }
            return false;
        }

        public int getRandom() {
            if (indexMap.size() == 0) {
                return -1;
            }
            while (true) {
                int t = (int) (Math.random() * list.size());
                if (list.get(t) != null) {
                    return list.get(t);
                }
            }
        }
    }

    public static void main(String[] args) {
        RandomizedSet randomizedSet = new RandomizedSet();
        System.err.println(randomizedSet.emptySet);
        System.err.println();
    }

}
